import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author LKQ
 * @date 2021/12/27 18:27
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        FrontMiddleBackQueue2 q = new FrontMiddleBackQueue2();
        q.pushFront(888438);   // [1]
        q.pushMiddle(772690);  // [1, 3, 2]
        q.pushMiddle(375192);  // [1, 4, 3, 2]
        q.pushFront(411268);
        q.pushFront(885613);
        q.pushMiddle(508187);
        q.popMiddle();
        q.popMiddle();
        q.pushMiddle(111498);
        q.pushMiddle(296008);
        q.popFront();
    }


}
class FrontMiddleBackQueue {

    Queue<Integer> q2;
    public FrontMiddleBackQueue() {
        q2 = new LinkedList<>();
    }

    public void pushFront(int val) {
        // 可以使用双端链表Deque，直接使用内部的addFirst()
        Queue<Integer> q1 = new LinkedList<>();
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        q2.offer(val);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }

        Deque<Integer> deque = new LinkedList<>();
    }

    public void pushMiddle(int val) {
        Queue<Integer> q1 = new LinkedList<>();
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        int size = q1.size() / 2;
        while (size > 0 && !q1.isEmpty()) {
            q2.offer(q1.poll());
            size--;
        }
        q2.offer(val);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
    }

    public void pushBack(int val) {
        Queue<Integer> q1 = new LinkedList<>();
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        q1.offer(val);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
    }

    public int popFront() {
        if (q2.isEmpty()) {
            return -1;
        }
        int val = q2.peek();
        q2.poll();
        return val;
    }

    public int popMiddle() {
        Queue<Integer> q1 = new LinkedList<>();
        if (q2.isEmpty()) {
            return -1;
        }
        int size = (q2.size()-1) / 2 ;
        while (size > 0 && !q2.isEmpty()) {
            q1.offer(q2.poll());
            size--;
        }
        int val = q2.peek();
        q2.poll();
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        q2 = q1;
        return val;

    }

    public int popBack() {
        Queue<Integer> q1 = new LinkedList<>();
        if (q2.isEmpty()) {
            return -1;
        }
        int size = q2.size() - 1;
        while (size > 0 ) {
            q1.offer(q2.poll());
            size--;
        }
        int val = q2.peek();
        q2.poll();
        q2 = q1;
        return val;
    }
}

class FrontMiddleBackQueue2 {
    Deque<Integer> deque;
    public FrontMiddleBackQueue2() {
        deque = new LinkedList<>();
    }

    public void pushFront(int val) {
        deque.addFirst(val);
    }

    public void pushMiddle(int val) {
        Stack<Integer> stack = new Stack<>();
        int size = deque.size() / 2;
        while (size > 0 ) {
            stack.push(deque.poll());
            size--;
        }
        deque.addFirst(val);
        while (!stack.isEmpty()) {
            deque.addFirst(stack.pop());
        }
    }

    public void pushBack(int val) {
        deque.addLast(val);
    }

    public int popFront() {
        if (deque.isEmpty()) {
            return -1;
        }
        int val = deque.peekFirst();
        deque.pollFirst();
        return val;

    }

    public int popMiddle() {
        if (deque.isEmpty()) {
            return -1;
        }
        Stack<Integer> stack = new Stack<>();
        int size = (deque.size()-1) / 2 ;
        while (size > 0) {
            stack.push(deque.poll());
            size--;
        }
        int val = deque.peekFirst();
        deque.pollFirst();
        while (!stack.isEmpty()) {
            deque.addFirst(stack.pop());
        }
        return val;
    }

    public int popBack() {
        if (deque.isEmpty()) {
            return -1;
        }
        int val = deque.peekLast();
        deque.pollLast();
        return val;
    }
}